
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct FS {
    int id;
    char ip[16];
    int num;
};

// 快排
int partition(struct FS arr[], int low, int high) {
    int random_idx = low + rand() % (high - low + 1);
    struct FS tmp = arr[random_idx];
    arr[random_idx] = arr[high];
    arr[high] = tmp;

    int pivot = arr[high].num;
    int i = (low - 1);
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j].num < pivot) {
            i++;
            // 交换结构体
            struct FS temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    struct FS temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

// int randomPartition(struct FS arr[], int low, int high) {
//     int randomIndex = low + rand() % (high - low + 1);
//     struct FS temp = arr[randomIndex];
//     arr[randomIndex] = arr[high];
//     arr[high] = temp;
//     return partition(arr, low, high);
// }

void quickSort(struct FS arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 二分排序
void binaryInsertionSort(struct FS arr[], int n) {
    for (int i = 1; i < n; i++) {
        struct FS key = arr[i];
        int left = 0;
        int right = i - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid].num > key.num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        
        arr[left] = key;
    }
}

int isSorted(struct FS arr[], int n) {
    for (int i = 1; i < n; i++) {
        if (arr[i].num < arr[i-1].num) {
            return 0;
        }
    }
    return 1;
}

int main() {
    // 测试
    const int SIZE = 100000;
    struct FS *fsArray = malloc(SIZE * sizeof(struct FS));
    srand(time(NULL));

    for (int i = 0; i < SIZE; i++) {
        fsArray[i].id = i + 1;
        sprintf(fsArray[i].ip, "192.168.1.%d", (i % 254) + 1); // 简单的IP模式
        fsArray[i].num = rand() % 100000;  
    }

    for (int i = 0; i < 10 && i < SIZE; i++) {
        printf("ID: %d, IP: %s, Num: %d\n", fsArray[i].id, fsArray[i].ip, fsArray[i].num);
    }

    clock_t start, end;
    double cpu_time_used;
    
    printf("\n开始排序111111111 %d 个数据...\n", SIZE);
    
    start = clock();
    quickSort(fsArray, 0, SIZE - 1);
    end = clock();
    
    int ret = isSorted(fsArray, SIZE);
    if (ret == 0) {
        printf("排序失败");
    }

    for (int i = 0; i < 10 && i < SIZE; i++) {
        printf("排序完成ID: %d, IP: %s, Num: %d\n", fsArray[i].id, fsArray[i].ip, fsArray[i].num);
    }

    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("\n排序 %d 个数据所需时间: %.6f 秒\n", SIZE, cpu_time_used);

    printf("\n开始排序22222222 %d 个数据...\n", SIZE);
    
    start = clock();
    quickSort(fsArray, 0, SIZE - 1);
    end = clock();
    
    ret = isSorted(fsArray, SIZE);
    if (ret == 0) {
        printf("排序失败");
    }
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("\n排序 %d 个数据所需时间: %.6f 秒\n", SIZE, cpu_time_used);

    printf("\n开始排序333333 %d 个数据...\n", SIZE);
    start = clock();
    quickSort(fsArray, 0, SIZE - 1);
    end = clock();
    
    ret = isSorted(fsArray, SIZE);
    if (ret == 0) {
        printf("排序失败");
    }
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("\n排序 %d 个数据所需时间: %.6f 秒\n", SIZE, cpu_time_used);

    return 0;
}